{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Clone Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: cloneGraph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #克隆图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你无向&nbsp;<strong><a href=\"https://baike.baidu.com/item/连通图/6460995?fr=aladdin\" target=\"_blank\">连通</a>&nbsp;</strong>图中一个节点的引用，请你返回该图的&nbsp;<a href=\"https://baike.baidu.com/item/深拷贝/22785317?fr=aladdin\" target=\"_blank\"><strong>深拷贝</strong></a>（克隆）。</p>\n",
    "\n",
    "<p>图中的每个节点都包含它的值 <code>val</code>（<code>int</code>） 和其邻居的列表（<code>list[Node]</code>）。</p>\n",
    "\n",
    "<pre>class Node {\n",
    "    public int val;\n",
    "    public List&lt;Node&gt; neighbors;\n",
    "}</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>测试用例格式：</strong></p>\n",
    "\n",
    "<p>简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（<code>val = 1</code>），第二个节点值为 2（<code>val = 2</code>），以此类推。该图在测试用例中使用邻接列表表示。</p>\n",
    "\n",
    "<p><strong>邻接列表</strong> 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。</p>\n",
    "\n",
    "<p>给定节点将始终是图中的第一个节点（值为 1）。你必须将&nbsp;<strong>给定节点的拷贝&nbsp;</strong>作为对克隆图的引用返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/01/133_clone_graph_question.png\" style=\"height: 500px; width: 500px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>adjList = [[2,4],[1,3],[2,4],[1,3]]\n",
    "<strong>输出：</strong>[[2,4],[1,3],[2,4],[1,3]]\n",
    "<strong>解释：\n",
    "</strong>图中有 4 个节点。\n",
    "节点 1 的值是 1，它有两个邻居：节点 2 和 4 。\n",
    "节点 2 的值是 2，它有两个邻居：节点 1 和 3 。\n",
    "节点 3 的值是 3，它有两个邻居：节点 2 和 4 。\n",
    "节点 4 的值是 4，它有两个邻居：节点 1 和 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/01/graph.png\" style=\"height: 148px; width: 163px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>adjList = [[]]\n",
    "<strong>输出：</strong>[[]]\n",
    "<strong>解释：</strong>输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>adjList = []\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>这个图是空的，它不含任何节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/01/graph-1.png\" style=\"height: 133px; width: 272px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>adjList = [[2],[1]]\n",
    "<strong>输出：</strong>[[2],[1]]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>节点数不超过 100 。</li>\n",
    "\t<li>每个节点值&nbsp;<code>Node.val</code> 都是唯一的，<code>1 &lt;= Node.val &lt;= 100</code>。</li>\n",
    "\t<li>无向图是一个<a href=\"https://baike.baidu.com/item/简单图/1680528?fr=aladdin\" target=\"_blank\">简单图</a>，这意味着图中没有重复的边，也没有自环。</li>\n",
    "\t<li>由于图是无向的，如果节点 <em>p</em> 是节点 <em>q</em> 的邻居，那么节点 <em>q</em> 也必须是节点 <em>p</em>&nbsp;的邻居。</li>\n",
    "\t<li>图是连通图，你可以从给定节点访问到所有节点。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [clone-graph](https://leetcode.cn/problems/clone-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [clone-graph](https://leetcode.cn/problems/clone-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,4],[1,3],[2,4],[1,3]]', '[[]]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        if not node:\n",
    "            return node\n",
    "        \n",
    "        cloned = {}\n",
    "        def clone(node):\n",
    "            if node in cloned:\n",
    "                return cloned[node]\n",
    "            new_node = Node(node.val)\n",
    "            cloned[node] = new_node\n",
    "            for neighbor in node.neighbors:\n",
    "                if neighbor not in cloned:\n",
    "                    new_node.neighbors.append(clone(neighbor))\n",
    "                else:\n",
    "                    new_node.neighbors.append(cloned[neighbor])\n",
    "            return new_node\n",
    "        \n",
    "        return clone(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, neighbors):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors\n",
    "\"\"\"\n",
    "import copy\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        return copy.deepcopy(node)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        if node != None:\n",
    "            d = {}\n",
    "            head = Node(node.val,[])\n",
    "            for e in node.neighbors:\n",
    "                head.neighbors.append(e)\n",
    "            d[node] = head\n",
    "            self.f(head, d)\n",
    "            return head\n",
    "        return None\n",
    "    def f(self,head,d):\n",
    "        # d是一个字典，用来保存原始结点 到 对应副本结点的映射\n",
    "        # r用来保存新创建的副本结点\n",
    "        r = []\n",
    "        for index,e in enumerate(head.neighbors):\n",
    "            # 如果原始结点不在d中，说明该原始结点还不在新图当中\n",
    "            if e not in d:\n",
    "                cur = Node(e.val, [])\n",
    "                for t in e.neighbors:\n",
    "                    cur.neighbors.append(t)\n",
    "                d[e] = cur\n",
    "                head.neighbors[index] = cur\n",
    "                r.append(cur)\n",
    "            # 若有原始借点在d中，说明该结点已经存在新图中\n",
    "            else:\n",
    "                head.neighbors[index] = d[e]\n",
    "        for i in r:\n",
    "            self.f(i, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = []):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        lookup = {}\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node: return\n",
    "            if node in lookup:\n",
    "                return lookup[node]\n",
    "            clone = Node(node.val, [])\n",
    "            lookup[node] = clone\n",
    "            for n in node.neighbors:\n",
    "                clone.neighbors.append(dfs(n))\n",
    "            \n",
    "            return clone\n",
    "\n",
    "        return dfs(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = []):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.node_list = {}\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        if node == None:\n",
    "            return node\n",
    "        if node in self.node_list:\n",
    "            return self.node_list[node]\n",
    "        clone = Node(node.val,[])\n",
    "        self.node_list[node]=clone\n",
    "        clone.neighbors = [self.cloneGraph(nei) for nei in node.neighbors]\n",
    "        return clone"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = []):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors\n",
    "\"\"\"\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        lookup = {}\n",
    "        def dfs(node):\n",
    "            if not node:return\n",
    "            if node in lookup:\n",
    "                return lookup[node]\n",
    "            clone = Node(node.val, [])\n",
    "            lookup[node] = clone\n",
    "            for n in node.neighbors:\n",
    "                lookup[node].neighbors.append(dfs(n))\n",
    "            return clone\n",
    "        return dfs(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = []):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.check ={}\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        if not node:\n",
    "            return node\n",
    "        if node in self.check:\n",
    "            return self.check[node]\n",
    "        clone_g = Node(node.val,[])\n",
    "        self.check[node]=clone_g\n",
    "        if node.neighbors:\n",
    "            clone_g.neighbors = [self.cloneGraph(n) for n in node.neighbors]\n",
    "        return clone_g\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        lookup = {}\n",
    "\n",
    "        def dfs(node):\n",
    "            #print(node.val)\n",
    "            if not node: return\n",
    "            if node in lookup:\n",
    "                return lookup[node]\n",
    "            clone = Node(node.val, [])\n",
    "            lookup[node] = clone\n",
    "            for n in node.neighbors:\n",
    "                clone.neighbors.append(dfs(n))\n",
    "            \n",
    "            return clone\n",
    "\n",
    "        return dfs(node)\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        from collections import deque\n",
    "        lookup = {}\n",
    "\n",
    "        def bfs(node):\n",
    "            if not node: return\n",
    "            clone = Node(node.val, [])\n",
    "            lookup[node] = clone\n",
    "            queue = deque()\n",
    "            queue.appendleft(node)\n",
    "            while queue:\n",
    "                tmp = queue.pop()\n",
    "                for n in tmp.neighbors:\n",
    "                    if n not in lookup:\n",
    "                        lookup[n] = Node(n.val, [])\n",
    "                        queue.appendleft(n)\n",
    "                    lookup[tmp].neighbors.append(lookup[n])\n",
    "            return clone\n",
    "\n",
    "        return bfs(node)\n",
    "'''\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> ' Node':\n",
    "        if not node:\n",
    "            return node\n",
    "        seen = {}\n",
    "        done = set()\n",
    "\n",
    "        def dfs(node_old):\n",
    "            val = node_old.val\n",
    "            if val in done:\n",
    "                return\n",
    "            done.add(val)\n",
    "            node_new = seen.setdefault(val, Node(val, []))\n",
    "            for neighbor in node_old.neighbors:\n",
    "                node_new.neighbors.append(seen.setdefault(neighbor.val, Node(neighbor.val, )))\n",
    "                dfs(neighbor)\n",
    "\n",
    "        dfs(node)\n",
    "        return seen[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visited = {}\n",
    "\n",
    "    def cloneGraph(self, node):\n",
    "        \"\"\"\n",
    "        :type node: Node\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        if not node:\n",
    "            return node\n",
    "\n",
    "        # 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回\n",
    "        if node in self.visited:\n",
    "            return self.visited[node]\n",
    "\n",
    "        # 克隆节点，注意到为了深拷贝我们不会克隆它的邻居的列表\n",
    "        clone_node = Node(node.val, [])\n",
    "\n",
    "        # 哈希表存储\n",
    "        self.visited[node] = clone_node\n",
    "\n",
    "        # 遍历该节点的邻居并更新克隆节点的邻居列表\n",
    "        if node.neighbors:\n",
    "            clone_node.neighbors = [self.cloneGraph(n) for n in node.neighbors]\n",
    "\n",
    "        return clone_node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        import copy\n",
    "        return copy.deepcopy(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from io import BytesIO\n",
    "from pickle import dump, load, dumps, loads\n",
    "from copy import deepcopy\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = []):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        return deepcopy(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = []):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        '''\n",
    "        dfs，然后逐个创建新的节点\n",
    "        '''\n",
    "        if node is None:\n",
    "            return None\n",
    "        \n",
    "        self.node_vis=collections.defaultdict(Node)\n",
    "        self.edge_vis=collections.defaultdict(int)\n",
    "\n",
    "        head=Node(1)\n",
    "        self.node_vis[1]=head\n",
    "\n",
    "        def dfs(cur_node,pre_node):\n",
    "            # print(cur_node.val,pre_node.val)\n",
    "            for next_node in cur_node.neighbors:\n",
    "                if self.edge_vis[(cur_node.val, next_node.val)]:\n",
    "                    continue\n",
    "                if next_node.val not in self.node_vis:\n",
    "                    cloned_next_node=Node(next_node.val)\n",
    "                    self.node_vis[next_node.val]=cloned_next_node\n",
    "                else:\n",
    "                    cloned_next_node=self.node_vis[next_node.val]\n",
    "                # print(f'add {pre_node.val}<->{cloned_next_node.val}')\n",
    "                pre_node.neighbors.append(cloned_next_node)\n",
    "                cloned_next_node.neighbors.append(pre_node)\n",
    "                self.edge_vis[(cur_node.val, next_node.val)]=1\n",
    "                self.edge_vis[(next_node.val, cur_node.val)]=1\n",
    "                dfs(next_node,cloned_next_node)\n",
    "\n",
    "        dfs(node,head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "\"\"\"\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def cloneNeighbor(self,node,neighbors):\n",
    "        for nb_node in neighbors:\n",
    "            if nb_node.val in self.record:\n",
    "                cp = self.record[nb_node.val]\n",
    "            else:\n",
    "                cp = Node(nb_node.val)\n",
    "                self.record[nb_node.val] = cp\n",
    "            if cp not in node.neighbors:\n",
    "                node.neighbors.append(cp)\n",
    "                self.cloneNeighbor(cp,nb_node.neighbors)\n",
    "        return \n",
    "\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        if not node:\n",
    "            return None \n",
    "        if not node.neighbors:\n",
    "            return Node(1) \n",
    "\n",
    "        self.record = {}\n",
    "\n",
    "        cp = Node(node.val)\n",
    "        self.record[node.val] = cp\n",
    "        self.cloneNeighbor(cp,node.neighbors)\n",
    "\n",
    "        return cp\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.hash_map = {}\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        if not node: return\n",
    "        if node.val in self.hash_map: return self.hash_map[node.val]\n",
    "        new = Node(node.val)\n",
    "        self.hash_map[node.val] = new\n",
    "        for neighbor in node.neighbors:\n",
    "            new.neighbors.append(self.cloneGraph(neighbor))\n",
    "        return new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        from collections import deque\n",
    "        lookup = {}\n",
    "\n",
    "        def bfs(node):\n",
    "            if not node: return\n",
    "            clone = Node(node.val, [])\n",
    "            lookup[node] = clone\n",
    "            queue = deque()\n",
    "            queue.appendleft(node)\n",
    "            while queue:\n",
    "                tmp = queue.pop()\n",
    "                for n in tmp.neighbors:\n",
    "                    if n not in lookup:\n",
    "                        lookup[n] = Node(n.val, [])\n",
    "                        queue.appendleft(n)\n",
    "                    lookup[tmp].neighbors.append(lookup[n])\n",
    "            return clone\n",
    "        return bfs(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        visited={}\n",
    "        def dfs(head):\n",
    "            if not head :\n",
    "                return None\n",
    "            if head in visited:\n",
    "                return visited[head]\n",
    "            n1=Node(head.val)\n",
    "            visited[head]=n1\n",
    "            \n",
    "            if  head.neighbors:\n",
    "                n1.neighbors=[  dfs(h)         for h in head.neighbors]\n",
    "            \n",
    "            return n1\n",
    "        return dfs(node)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        visited={}\n",
    "        def dfs(head):\n",
    "            if not head :\n",
    "                return None\n",
    "            if head in visited:\n",
    "                return visited[head]\n",
    "            n1=Node(head.val)\n",
    "            visited[head]=n1\n",
    "            \n",
    "            if  head.neighbors:\n",
    "                n1.neighbors=[  dfs(h)         for h in head.neighbors]\n",
    "            \n",
    "            return n1\n",
    "        return dfs(node)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        return copy.deepcopy(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        if not node:\n",
    "            return None\n",
    "        # print(node.neighbors[1].val)\n",
    "        record = [[] for i in range(101)]\n",
    "        visited = []\n",
    "        cur = node\n",
    "        queue = []\n",
    "        queue.append(cur)\n",
    "        while len(queue) >0:\n",
    "            print(len(queue))\n",
    "            cur_node = queue.pop(0)\n",
    "            # print(len(queue))\n",
    "            # print(cur_node.val, visited)\n",
    "            print(type(cur_node))\n",
    "            if cur_node.val not in visited:\n",
    "                # print(visited)\n",
    "                N = Node(cur_node.val)\n",
    "                record[cur_node.val].append(N)\n",
    "                visited.append(cur_node.val)\n",
    "                length = len(cur_node.neighbors)\n",
    "                nei = []\n",
    "                for i in range(length):\n",
    "                    # print(cur_node.val, cur_node.neighbors[i].val)\n",
    "                    queue.append(cur_node.neighbors[i])\n",
    "                    if cur_node.neighbors[i].val not in record:\n",
    "                        record[cur_node.neighbors[i].val].append(Node(cur_node.neighbors[i].val))\n",
    "                    nei.append(record[cur_node.neighbors[i].val][0])\n",
    "                # print(len(queue))\n",
    "                record[cur_node.val][0].neighbors = nei\n",
    "        \n",
    "        return record[1][0] \n",
    "           \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "from typing import Optional\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:\n",
    "        if not node:\n",
    "            return None\n",
    "        stack = collections.deque([node])\n",
    "        # 已经初始化的节点\n",
    "        memo = {node: Node(node.val)}\n",
    "\n",
    "        while stack:\n",
    "            cur = stack.popleft()\n",
    "            for ori_adj in cur.neighbors:\n",
    "                if ori_adj not in memo:\n",
    "                    memo[ori_adj] = Node(ori_adj.val)\n",
    "                    stack.append(ori_adj)\n",
    "                memo[cur].neighbors.append(memo[ori_adj])\n",
    "        return memo[node]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "from typing import Optional\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:\n",
    "        lookup = {}\n",
    "\n",
    "        def bfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            queue = deque([node])\n",
    "            root = Node(node.val,[])\n",
    "            lookup[node.val] = root\n",
    "            while queue:\n",
    "                tempOld = queue.popleft()\n",
    "                if tempOld.neighbors:\n",
    "                    tempNew = lookup[tempOld.val]\n",
    "                    for neighbors in tempOld.neighbors:\n",
    "                        if neighbors.val not in lookup:\n",
    "                            lookup[neighbors.val] = Node(neighbors.val,[])\n",
    "                            queue.append(neighbors)\n",
    "                        tempNew.neighbors.append(lookup[neighbors.val])\n",
    "            return root\n",
    "\n",
    "        return bfs(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val = 0, neighbors = None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\"\"\"\n",
    "\n",
    "from typing import Optional\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:\n",
    "        lookup = {}\n",
    "\n",
    "        def bfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            queue = deque([node])\n",
    "            root = Node(node.val,[])\n",
    "            lookup[node.val] = root\n",
    "            while queue:\n",
    "                tempOld = queue.popleft()\n",
    "                if tempOld.neighbors:\n",
    "                    tempNew = lookup[tempOld.val]\n",
    "                    for neighbors in tempOld.neighbors:\n",
    "                        if neighbors.val not in lookup:\n",
    "                            lookup[neighbors.val] = Node(neighbors.val,[])\n",
    "                            queue.append(neighbors)\n",
    "                        tempNew.neighbors.append(lookup[neighbors.val])\n",
    "            return root\n",
    "\n",
    "        return bfs(node)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
